In DMT/OFDM systems, bits in a transmit data stream are divided up into symbols which are then grouped and used to modulate a number of carriers. Each carrier is modulated using either Quadrature Amplitude Modulation (QAM), or Quadrature Phase Shift Keying (QPSK) and, dependent upon the characteristics of the carrier's channel, the number of source bits allocated to each carrier will vary from carrier to carrier. In the transmit mode, inverse Fast Fourier Transforms (iFFT's) are used to convert QAM modulated pairs into symbols for the transmitted signal. In the receive direction, Fast Fourier Transforms (FFT's) are used before QAM demodulation.
In typical systems, the discrete Fourier transform (DFT) or inverse discrete Fourier transform (iDFT) is performed using the Fast Fourier transform (FFT) operation. The FFT has the advantage that the number of operations compared to the DFT is significantly reduced. A “N” point DFT requires N^2 operations whilst an “N” point FFT requires N log2(N)/2 operations, a considerable saving.
As has already been noted the transmitter requires an inverse FFT while the receiver requires an FFT. In DMT systems, such as ADSL, these operations are typically performed by separate hardware or software modules or a single, double speed module used alternately for receive and transmit. An object of the present invention is how to make this less complex by using a single normal speed module, in hardware or software, to implement both functions, since this will result in a considerable reduction in computational complexity, besides less expense for silicon.
It is known from an article “ADSL, VDSL and Multicarrier Modulation” by John A. C. Bingham (John Wiley & Sons), that if the data for a FFT is only real valued, by packing odd and even samples into a complex array of half the original length, the FFT size may be reduced to half. The resultant, complex data output is separated by:                (1) Pre-processing the data such that when an iFFT is performed the real par contains even time samples and the imaginary part odd time samples:Y[i]={X(i)+X*(N−i)]+j[X(i)−X*(N−i)W^(N−i)}*        (where N is the size of the transform, e.g. a 256 point complex vector and X* is the complex conjugate).        (2) Providing an input to the FFT which is a 256 point complex vector formed from the real 2N point data: the real part containing even sample points and the imaginary part odd sample points and post processing the FFT output:Y[i]=0.5[X(i)+X*(N−i)]−j/2[X(i)−X*(N−i)]W^1        (where W is the butterfly factor)        
There are several variations on this technique including maintaining the original FFT size and then packing two real arrays into a single complex array; a simple post processing operation being used to separate the data. The technique is described in “Handbook of Real Time FFTs” by Winthrop Smith and Joanne Smith (IEEE press), the basic steps are:
Let:                a(n) and b(n) be real vectors of length N, let:c(n)=a(n)+jb(n) (where j is the square root of −1).        
Let:C(k)=FFT[c(n)]=R(k)+jI(k) where k=0, 1, 2, . . . (N−1)
The complex transforms, A(k) and B(k), of the original vectors are now separated using, for example:
for (k = 1; k++,k <=(N−2)/2) {RP(k) = RP(N−k) = (R(k) + R(N−k))/2RM(k) = −RM(N−k) = (R(k) − R(N−k))/2IP(k) = IP(N−k) = (I(k) + I(N−k)))/2IM(k) = −IM(N−k) = (I(k) − I(N−k)))/2}RP(0) = R(0)IP(0) = I(0)RM(0) = IM(0) = RM(N/2) = IM(N/2) = 0RP(N/2) = R(N/2)IP(N/2) = I(N/2)(where P and M are respectively..........please identify...)
Finally (and for example):
for (k = 0; k++, k <=(N−1)) {A(k) = RP(k) + jIM(k)B(k) = IP(k) − jRM(k)}
Transforming two real arrays at the same time is potentially more efficient but overall the technique has the disadvantage that the overall latency for data is doubled. Some services, such as digitised voice, have strict latency requirements and this additional delay may be unacceptable.